#include<queue>
using std::queue;


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 用层次遍历
        // 检查每层镜像对称
        if (root == nullptr) return true;
        int n;
        queue<TreeNode*> leftLayer;
        if (root->left) leftLayer.push(root->left);
        queue<TreeNode*> rightLayer;
        if (root->right) rightLayer.push(root->right);
        while (true) {
            queue<TreeNode*> newLeft, newRight;
            if (leftLayer.size() != rightLayer.size()) return false;
            if (leftLayer.size() == 0) break;
            while (!leftLayer.empty()) {
                auto left = leftLayer.front();
                auto right = rightLayer.front();
                leftLayer.pop();
                rightLayer.pop();
                if (left->val == right->val && isTwoNodeSymmetric(left, right)) {
                    // 两点结构对称且值相同
                    if (left->left) {
                        newLeft.push(left->left);
                        newRight.push(right->right);
                    }
                    if (left->right) {
                        newLeft.push(left->right);
                        newRight.push(right->left);
                    }
                }
                else return false;
            }
            leftLayer = newLeft;
            rightLayer = newRight;
        }
        return true;
    }
    bool isTwoNodeSymmetric(TreeNode* a, TreeNode* b) {
        // 默认a/b不为null
        
        if ((a->left && !b->right) || (!a->left && b->right) || (a->right && !b->left) || (!a->right && b->left))
            return false;
        return true;
    }
};